/*************************************************************************
> File Name: greedy.cpp
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2024-01-13 15:14:47
> Description:
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
************************************************************************/

// 思路： 贪心
// 记录跳跃一次的又边距，在这个距离内找到一个最大值。
// 当到达右边距时，完成本次起跳，进行下一次起跳
// tips： 虽然跳跃距离各不相同，但是他们跳跃后距离初始点的距离是可以比较的

#include <vector>
using namespace std;

class Solution
{
public:
    int jump(vector<int> &nums)
    {
        int right = 0, max_far = 0, step = 0, max_, length = nums.size();

        for (int i = 0; i < length; i++)
        {
            if (max_far < i + nums[i])
            {
                max_far = i + nums[i];
            }
            if (right == i && right != length - 1) // 右边界刚好到达末尾，则不需要跳下一次
            {
                right = max_far;
                step++;
            }
        }
        return step;
    }
};